	\chapter{Výsledky}
	V~této kapitole budou zmíněny a analyzovány výsledky, bude zde uvedeno
	několik grafů, na kterých bude tato analýza založena.

	Grafy jsou založeny na náhodně vygenerovaných vstupních maticích
	s~rovnoměrným rozložením pravděpodobnosti. V~každém případě se graf
	sestává z~30 vzorků pro jednu velikost problému\footnote{Velikost
		problému je dána počtem řádků matice. V~našem případě je matice
	vždy čtvercová. Tedy počet úloh rostl s~druhou mocninou velikosti
	problému.}. Testy jsem prováděl na
	počítači s~procesorem Genuine Intel T1350 (1.86GHz) s~OS linux (jádro
			2.6.20-15), verzí Matlabu 7.3.0.298 (R2006b) a program
	byl přeložen pomocí gcc-3.4.

	\section{Job-shop}
	\startfiguretext
		[right]
		[fig:JSPROCENTA]{Procento vyřešených Job-shop problémů velikosti 5 v~čase.}
	{\externalfigure[images/vysledky/JOBSHOP/DFS_JOBSHOPpercent_s5_8_5__13_3][width=0.5\makeupwidth]}
		Závislost doby běhu výpočtu na velikosti Job-shop problému je na
		obrázku  \in[fig:JS]. Graf není neklesající funkcí, jak by se dalo očekávat. Je to způsobeno
		tím, že na řešení některých problémů (řádově do 5\%) se
		spotřebuje velmi velké monožství času, zatímco  ostatní jsou
		hotovy hned (prořezávání domén je otázkou několika ms). Tento
		jev je dobře vidět na obrázku \in[fig:JSPROCENTA], kde se 2
		problémy řešily dlouho a ostatní byly vyřešeny hned. S~takovou
		situací se střetáváme při většině velikostí problémů větších než
		5.


	\stopfiguretext

		Jednoznačným závěrem je, že algoritmus není robustní. A~to
		hlavně kvůli tomu, že se prohledávání dostává do takových
		oblastí grafu, kde to není zapotřebí. V~knihovně gecode bohužel
		není naimplementován Edge-finder, který by výpočet nejspíše dost
		urychlil, ale hlavně by pak nedocházelo k~tak velkému kolísání
		v~uvedených grafech.
		Na druhou stranu tento algoritmus vyřeší v~celku rychle
		komplexní benchmarky - například ft6 za 300ms.


		
		DFS i BAB jsou v~našem případě shodnými algoritmy a výsledky na to ukazují. Oba dva řešily problém řádově stejně rychle a robustnost byla podobná. Otázkou je, jak by se choval algoritmus LDS.

			
	\placefigure
	  []
	  [fig:JS]
	  {Porovnání doby řešení různě velkých Job-shop problémů různými prohledávacími
		  algoritmy (časy jsou v~logaritmech).}
	{\startcombination[2*1]
	    {\externalfigure[images/vysledky/JOBSHOP/DFS_JOBSHOPruntime_log__min1max7__8_5__13_4][width=0.5\makeupwidth]}
		    {DFS}
	    {\externalfigure[images/vysledky/JOBSHOP/BAB_JOBSHOPruntime_log__min1max7__8_5__13_9][width=0.5\makeupwidth]}
	    {BAB}
	  \stopcombination
	}

	\section{Flow-shop}

	\startfiguretext
		[left]
		[fig:FSPROCENTA]{Procento vyřešených Flow-shop problémů velikosti 7 v~čase.}
	{\externalfigure[images/vysledky/FLOWSHOP/DFS_FLOWSHOPpercent_s7_8_5__12_50][width=0.5\makeupwidth]}
	Porovnání algoritmů DFS a BAB (obrázek \in[fig:FS]) pro tento případ dopadne stejně. Oba
	algoritmy řeší Flow-shop zhruba stejně rychle. Bez větších výkyvů a
	křivka je podle předpokladu rostoucí.

	I~rozptyl doby trvání řešení se snížil v~porovnání s~Job-shopem. Ukazuje
	to obrázek \in[fig:FSPROCENTA].
	\stopfiguretext



	\placefigure
	  [force,here]
	  [fig:FS]
	  {Porovnání doby řešení různě velkých Flow-shop problémů různými prohledávacími
		  algoritmy (časy jsou v~logaritmech).}
	{\startcombination[2*1]
	    {\externalfigure[images/vysledky/FLOWSHOP/DFS_FLOWSHOPruntime_log__min1max7__8_5__12_50][width=0.5\makeupwidth]}
		    {DFS}
	    {\externalfigure[images/vysledky/FLOWSHOP/BAB_FLOWSHOPruntime_log__min1max7__8_5__12_44][width=0.5\makeupwidth]}
	    {BAB}
	  \stopcombination
	}


	\section{Open-shop}


\startfiguretext
	[left]
	[fig:OSPROCENTA]{Procento vyřešených problémů Open-shop velikosti 4 v~čase.}
{\externalfigure[images/vysledky/OPENSHOP/BAB_OPENSHOPpercent_s4_8_5__13_40][width=0.5\makeupwidth]}
Známky, které vykazovaly algoritmy u~řešení Job-shopu, jsou stejné i
u~Open-shopu. Velké výkyvy doby běhu, nižší robustnost - obrázek \in[fig:OS]
		porovnává DFS a BAB, \in[fig:OSPROCENTA] ukazuje
		procento vyřešení v~čase. I~zde se většinou najde jedno
		zadání, které trvá delší dobu.
\stopfiguretext

\placefigure
  []
  [fig:OS]
  {Porovnání doby řešení různě velkých Open-shop problémů různými prohledávacími
	  algoritmy (časy jsou v~logaritmech).}
{\startcombination[2*1]
	    {\externalfigure[images/vysledky/OPENSHOP/DFS_OPENSHOPruntime_log__min1max7__8_5__12_51][width=0.5\makeupwidth]}
	    {DFS}
    {\externalfigure[images/vysledky/OPENSHOP/BAB_OPENSHOPruntime_log__min1max7__8_5__13_40][width=0.5\makeupwidth]}
    {BAB}
  \stopcombination
}

